package day05;

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}

public class 重排链表 {
    public void reorderList(ListNode head) {
        // 判断边界条件
        if (head == null || head.next == null || head.next.next == null) {
            return;
        }
        // 两种情况：链表个数为偶数、链表个数为奇数
        // 定义慢指针
        ListNode slow = head;
        // 定义快指针
        ListNode fast = head;
        // 利用循环，结束条件是判断快指针是否走到最后
        // 如果是奇数，结束时慢指针指向中间的呢个结点，快指针指向最后一个结点
        // 如果是偶数，结束时慢指针指向第二个中间结点，快指针指向最后一个节点的下一个结点
        while (fast != null && fast.next != null) {
            // 快指针先走
            fast = fast.next.next;
            // 慢指针接着走
            slow = slow.next;
        }
        // 此时不管链表的个数是奇数还是偶数，slow指向中间的结点
        // 定义新的节点指向中间结点的下一个结点
        ListNode cur = slow.next;
        // 将中间结点的next置为空
        slow.next = null;
        // 将后半部分的节点进行逆转,利用头插法或者尾插法
        // 这里用头插法
        // 定义一个虚拟节点
        ListNode head2 = new ListNode(0);
        while (cur != null) {
            // 记录下一个结点
            ListNode curNext = cur.next;
            cur.next = head2.next;
            head2.next = cur;
            cur = curNext;
        }
        // 合并两个链表
        // 定义新的结点和虚拟节点
        ListNode cur1 = head, cur2 = head2.next;
        ListNode ret = new ListNode(0);
        ListNode prev = ret;
        while (cur1 != null) {
            prev.next = cur1;
            prev = cur1;
            cur1 = cur1.next;
            if (cur2 != null) {
                prev.next = cur2;
                prev = cur2;
                cur2 = cur2.next;
            }
        }
    }
}
